package com.data.basic.chapter04;

import java.util.HashMap;

/** 链表的实现  =====>  引入了虚拟头结点dummyHead
 *      {null}→[0]→1→2→3→4→5→6→null
 *      [] 表示head指向的位置，方向为单向
 *      {} 表示dummyHead的节点
 * Created by wangbing on 2018/5/2.
 */
public class LinkedListDemo02<E> {
    private Node dummyHead;
    private int size;

    public LinkedListDemo02() {
        dummyHead=new Node(null,null);
        size=0;
    }

    /**
     * 获取链表的元素个数
     * @param
     */
    public int  getSize(){
        return size;

    }

    /**
     * 返回链表是否为空
     * @param
     */

    public boolean isEmpty(){
        return size==0;
    }

    /**
     * 链表插入---单链表头部插入
     * @param
     */
    public void addFirst(E e){
        add(e,0);

    }

    /**
     *
     * @param e
     * @param index
     */
    public void add(E e,int index){
        if (index<0||index>size){
            throw new IllegalArgumentException("数组越界");
        }
        Node prev = dummyHead;

//        定位到index-1的位置  ；找到待添加节点的前一个节点
        for (int i=0;i<index;i++){
            prev = prev.next;
        }
//        Node insertNode = new Node(e);
//        insertNode.next = beforeIndex.next;
//        beforeIndex.next = insertNode;
       prev.next = new Node(e,prev.next);

        size++;
    }

    /**
     * 在链表尾部插入一个元素
     * @param e
     */
    public void addLast(E e){
        add(e,size);
    }

    /**
     * 按照索引获得元素
     * @param index
     * @return
     */
    public E get(int index ){
        if (index<0||index>=size){
            throw new IllegalArgumentException("get failed,illegal index");
        }
        Node cur = dummyHead.next;
        for (int i=0;i<index;i++){
            cur = cur.next;
        }
        return (E) cur.e;

    }

    public E getFirst(){
        return get(0);
    }
    public E getLast(){
        return get(size-1);
    }

    /**
     * 设置链表的元素
     * @param e
     * @param index
     */
    public void set(E e,int index){
        if (index<0||index>=size){
            throw new IllegalArgumentException("set failed,illegal index");
        }
        Node node = dummyHead.next;
        for (int i=0;i<index;i++){
            node = dummyHead.next;
        }
        node.e= e;
    }

    /**
     * 链表的遍历
     * @param e
     * @return
     */
    public boolean contains(E e){
        Node cur = dummyHead.next;
        while(cur!=null){
            if (cur.e==e){
                return true;
            }
        }
        return false;
    }

    /**
     * 按照索引删除链表的元素
     * @param index
     */
    public E remove(int index){
        if (index<0||index>size){
            throw new IllegalArgumentException("del index  outOfList");
        }
        Node prev = dummyHead;
        for (int i =0;i<index;i++){
            prev=prev.next;
        }
        // 要删除的节点
        Node retNode = prev.next;

        prev.next = prev.next.next;
        retNode.next=null;

        size--;
        return (E) retNode.e;
    }
    public E removeFirst(){
        return remove(0);
    }

    public E removeLast(){
        return remove(size);
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
//        Node cur = dummyHead.next;
//        while (cur!=null){
//            res.append(cur+"->");
//            cur = cur.next;
//        }

        for ( Node cur =dummyHead.next;cur!=null;cur=cur.next){
            res.append(cur+"->");
//            cur = cur.next;
        }
        res.append("NULL");
        return res.toString();
    }

    private class Node<E>{
        /**
         * 单链表的节点类
         */
        public E e;
        public Node next;

        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }

        public Node(E e) {
            this(e,null);
        }

        public Node() {
            this(null,null);
        }

        @Override
        public String toString() {
            return e.toString();
        }
    }


    public static void main(String[] args) {
        LinkedListDemo02<Integer> list = new LinkedListDemo02();
        for (int i=0;i<6;i++){
            list.addFirst(i);
            System.out.println(list);
        }
        list.add(777,4);
        System.out.println(list);
        list.remove(4);
        System.out.println(list);
    }
}
